package leet203removelinkedlistitem

type ListNode struct {
	Val  int
	Next *ListNode
}

// removeElements removes all elements from a linked list of integers that have value val.
// Given the head of the linked list and an integer val, remove all the nodes with value val,
// and return the new head.
// You must do this by modifying the list in place with O(1) extra memory.
// Example 1:
// Input: head = [1,2,6,3,4,5,6], val = 6
// Output: [1,2,3,4,5]
// Example 2:
// Input: head = [], val = 1
// Output: []
// Example 3:
// Input: head = [7,7,7,7], val = 7
// Output: []
// Constraints:
// The number of nodes in the list is in the range [0, 10^4].
// 1 <= Node.val <= 50
// 0 <= k <= 10^4
// The value of each node in the list is in the range [1, 100].
// Follow up: Could you do this in one pass?
func removeElements(head *ListNode, val int) *ListNode {
	if head == nil {
		return nil
	}
	// dummy node to handle edge cases
	// 这是一个虚拟头节点，方便处理删除头节点的情况
	// 例如：1->2->3->4->5->6, 删除1
	dummy := &ListNode{Next: head}
	current := dummy
	// current相当于当前节点的引用
	// 只要该引用的下一个节点不为空，就继续遍历，我们已经将head节点初始化为虚拟头结点的Next了，所以head节点也会被遍历到，和其他节点一样了。
	for current.Next != nil {
		// 找到目标值就将他的前进指针指向更下一个
		if current.Next.Val == val {
			current.Next = current.Next.Next
		} else {
			current = current.Next
		}
	}
	return dummy.Next
}